package solution;

import java.util.*;
import java.util.stream.Collectors;

// 无向图
// 邻接表实现
public class AdjacencyListGraph<V> implements Graph<V> {
    private Map<V, Set<Edge<V>>> adj;

    public AdjacencyListGraph() {
        this.adj = new HashMap<>();
    }

    @Override
    public Set<V> vertices(){
        return adj.keySet();
    }

    @Override
    public Set<Edge<V>> edges(){

        Set<Edge<V>> edges = new HashSet<>();
        Set<String> uniqueKeys = new HashSet<>();

        for (Set<Edge<V>> value : adj.values()) {
            for (Edge<V> edge : value) {
                if (edge == null) {
                    continue;
                }

                String fromStr = edge.getFrom().toString();
                String toStr = edge.getTo().toString();

                // 规范化无向边的唯一标识，例如 "0-2" 与 "2-0" 视为同一条边
                String key = fromStr.compareTo(toStr) < 0 ? fromStr + "-" + toStr : toStr + "-" + fromStr;

                if (!uniqueKeys.contains(key)) {
                    uniqueKeys.add(key);
                    edges.add(edge);
                }
            }
        }

        return edges;
    }

    @Override
    public void addEdge(V from, V to){
        addEdge(from, to, 0.0d);
    }

    @Override
    public void addEdge(V from, V to, double weight){
        adj.putIfAbsent(from, new HashSet<>());
        adj.putIfAbsent(to, new HashSet<>());

        adj.get(from).add(new Edge<>(from, to, weight));
        adj.get(to).add(new Edge<>(to, from, weight));
    }

    @Override
    public Set<Edge<V>> neighbors(V v){
        return adj.getOrDefault(v, Set.of()).stream().collect(Collectors.toSet());
    }

    @Override
    public void addVertex(V v) {
        adj.putIfAbsent(v, new HashSet<>());
    }
}
